//
//  CLLeetCodeAlgorithm.m
//  Charles
//
//  Created by Charles on 2020/3/24.
//  Copyright © 2020 charles. All rights reserved.
//

#import "CLLeetCodeAlgorithm.h"

@implementation CLLeetCodeAlgorithm
/**
基本思想：
ASCII一共有127种，因此采用大小为127的hash表。首先初始化第一个字符，同时初始化第一个字符的哈希表。然后从第二个字符开始遍历字符串。遍历时遵循以下原则：
1 当前元素x不在哈希表中时，将子串长度加1，并将该元素对应的表项置为1；
2 当前元素x在哈希表中时，即代表当前字串存在重复元素，记录当前字串长度后，考虑如下原则：
2.1 当前元素x与x后一个元素是否相同，如果不同，则证明下一个子串从x开始，因此重置哈希表和子串长度；如果相同，则指向下一个元素。
2.1.1 寻找当前子串中第一个在x后面不为x的元素y。将y作为新子串的起始元素，开始向后遍历。
3 由于题目要求最长子串，因此要记录子串的长度，代码中所采用的思想是利用中间变量temp，每次更新子串长度时都与temp比较，如果当前子串长度大于temp则让temp记录新的子串长度。
*/
int maxSubStringLength(char *string){
    if (!strlen(string)) {
        return 0;
    }
    if (strlen(string) == 1) {
        return 1;
    }
    
    int hashMap[127] = {0}; // 创建哈希表
    int maxLength = 1;      // 最大子串长度
    int originLength = 1;   // 子串初始长度
    
    hashMap[string[0] % 127] = 1; // 初始化首元素哈希表
    
    for (int i = 1; i < string[i] != '\0' ; i++) {
        printf("char is %c \n",string[i]);
        // 如果当前元素在子串中
        if (hashMap[string[i] % 127] == 1) {
            // 重置长度
            originLength = 1;
            // 判断是否切换新子串开始遍历
            if (string[i+1] != '\0' && (string[i] != string[i+1])) {
                memset(hashMap, 0, 127 * sizeof(int));
                // 回溯子串，定位下一个子串的位置
                for (int j = i - 1; j >= 0; j--) {
                    if (string[j] == string[i]) {
                        i = j + 1;
                        hashMap[string[i] % 127] = 1;
                        break;
                    }
                }
            }
            continue;
        }else {
            originLength++;
            hashMap[string[i] % 127] = 1;
            if (originLength > maxLength) {
                maxLength = originLength;   // 更新最大长度
            }
        }
    }
    return maxLength;
}


int findMeidanWithTwoSortedArray(){
    return 0;
}

+ (NSArray *)findTwonumum:(NSArray *)nums target:(int)target{
    NSMutableDictionary *hasMap = [NSMutableDictionary new];
    NSArray *resultArray = nil;
    for (int index = 0; index < nums.count; index++) {
        int temp = target - [[nums objectAtIndex:index] intValue];
        if (![hasMap objectForKey:@(temp)]) {
            [hasMap setObject:@(index) forKey:[nums objectAtIndex:index]];
        }else {
            resultArray = @[[hasMap objectForKey:@(temp)],@(index)];
        }
    }
    return resultArray;
}

@end
